Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

题目大意：给定数组，返回连续子数组的最大和。

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/5/25
 * 时间复杂度O(N),sum记录临时和,发现sum为负数为置为0,因为为负数,舍去前面的值和更大
 */
public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int len = nums.length;
        int result = nums[0];
        int sum = 0;

        for (int i = 0; i < len; i++) {
            sum += nums[i];
            result = Math.max(result, sum);
            sum = Math.max(0, sum);
        }
        return result;
    }
}